
//自己实现一个简单的顺序表
//直接以int为例就行，就不写泛型了
public class MyArrayList {
    //真正存储数据。顺序表本身就是基于数组的封装
    private int[] arr;
    //约定arr中的钱size个元素，表示有效元素个数
    private int size = 0;

    //***************************************************************
    public MyArrayList() {
        //无参版本
        arr = new int[10];
    }

    public MyArrayList(int capacity) {
        arr = new int[capacity];
    }

    public int size() {
        return size;
    }

    //新增元素。尾插
    public void add(int val) {
        //把新的元素放到最后一个位置上，下标为size的位置
        //[0,size)区间
        if (size == arr.length) {
            //数组满了，先扩容
            resize();
        }
        arr[size] = val;
        size++;
    }

    private void resize() {
        //1.创建一个更长的数组，容量扩展到1.5倍
        int[] newArr = new int[(int) (arr.length * 1.5)];
        //2.把原来数组的元素复制到新数组上
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[i];
        }
        //3.用新的数组代替旧数组
        //此时旧的数组就会被垃圾回收机制给释放掉
        arr = newArr;
    }

    //任意位置新增
    public void add(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        //如果数组已经满了，继续添加元素，也要先扩容
        if (size == arr.length) {
            resize();
        }
        //搬运元素，从后往前，依次把每个元素都往后搬运一个位置
        //如果元素本身下标是i，就把这个元素赋值到i+1的位置上
        //index位置的元素也需要往后搬运一下，i>=index
        for (int i = size - 1; i >= index; i--) {
            arr[i + 1] = arr[i];
        }
        //此时index的位置已经腾出来了
        arr[index] = val;
        //不要忘记更新size
        size++;

    }

    //根据下标获取元素
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界" + index);
        }
        return arr[index];
    }

    //根据下标设置元素
    public void set(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("下标越界" + index);
        }
        arr[index] = val;
    }

    //删除元素，按照下标来删除
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界" + index);
        }
        int result = arr[index];

        //这个逻辑就已经覆盖了下面的一般情况
        if (index == size - 1) {
            size--;
            return result;
        }

        for (int i = index; i < size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        size--;
        return result;
    }

    //删除元素，按照值来删除
    public void delete(int val) {
//        int index = 0;
//        for (index = 0; index < size; index++) {
//            if (arr[index] == val) {
//                break;
//            }
//        }
        int index = indexOf(val);
        if (index==-1){
            return;
        }

//        if (index == size) {
//            return;
//        }
//        for (int i = index;i < size-1;i++){
//            arr[i] = arr[i+1];
//        }
//        size--;
        remove(index);
    }

    //判断元素是否存在
    public boolean contains(int val) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return true;
            }
        }
        return false;
    }

    //查找元素所在位置
    public int indexOf(int val) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }

    //从后往前找
    public int lastIndexOf(int val) {
        for (int i = size - 1; i >= 0; i--) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }

    //清空
    public void clear() {
        //删除所有元素
        //逻辑删除即可
        size =0;
    }

    //打印操作，搞一个tostring 把myarraylist转化成字符串
    @Override
    public String toString() {
        //打印格式形如：[1,2,3,4]
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(arr[i]);
            if (i < size - 1) {
                //最后一个元素
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //**************************************************************************
    public static void test1() {
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);

        if (list.contains(3)) {
            System.out.println("OK");
        } else {
            System.out.println("不通过");
        }

        if (!list.contains(100)){
            System.out.println("OK");
        }else {
            System.out.println("no");
        }

        if (list.indexOf(5)==4){
            System.out.println("OK");
        }else {
            System.out.println("No");
        }

        if (list.indexOf(100)==-1){
            System.out.println("OK");
        }else {
            System.out.println("NO");
        }


        System.out.println(list.contains(3));
        System.out.println(list.contains(100));
        System.out.println(list.indexOf(5));
        System.out.println(list.indexOf(100));
    }

    public static void main(String[] args) {
        test1();
    }
}
